package binarySearch;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author pengfei.hpf
 * @date 2020/3/14
 * @verdion 1.0.0
 * 792. 匹配子序列的单词数
 * 给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
 *
 * 示例:
 * 输入:
 * S = "abcde"
 * words = ["a", "bb", "acd", "ace"]
 * 输出: 3
 * 解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
 * 注意:
 *
 * 所有在words和 S 里的单词都只由小写字母组成。
 * S 的长度在 [1, 50000]。
 * words 的长度在 [1, 5000]。
 * words[i]的长度在[1, 50]。
 */
public class NumMatchingSubseq {
    public int numMatchingSubseq(String S, String[] words) {
        if(S == null || S.length() == 0){
            return 0;
        }
        Map<Character, List<Integer>> map = new HashMap<>();
        char[] chars = S.toCharArray();
        for(int i = 0; i < chars.length; i++){
            map.computeIfAbsent(chars[i], x-> new ArrayList<Integer>()).add(i);
        }
        int len = S.length();
        int count = 0;
        for(String str: words){
            int lastIndex = -1;
            int i = 0;
            boolean found = true;
            while( i < str.length()){
                char c = str.charAt(i);
                List<Integer> list = map.get(c);
                if(list != null){
                    lastIndex++;
                    int left = 0;
                    int right = list.size();
                    while(left < right){
                        int mid = (left + right)/2;
                        if(lastIndex > list.get(mid)){
                            left = mid + 1;
                        } else {
                            right = mid;
                        }
                    }
                    if(left < list.size()){
                        lastIndex = list.get(left);
                    } else {
                        found = false;
                        break;
                    }
                } else {
                    found = false;
                    break;
                }
                i ++;
            }
            if(found){
                count ++;
            }
        }
        return count;
    }
}
